package com.shawn.leetcode.array.one;

import java.util.Arrays;

/**
 *
 */
public class FirstMissingPositive {

	public int firstMissingPositive(int[] nums) {
		if(nums == null || nums.length == 0){
			return 1;
		}
		Arrays.sort(nums);
		int result = 0;
		int mark = 0;
		for (int i = 0; i < nums.length; i++) {
			// 找到正数
			if(nums[i] <= 0){
				if(i == nums.length - 1){
					result = 1;
				}
				continue;
			}
			mark ++;
			// 对正数处理
			if(nums[i] > 1 && mark == 1){
				result = 1;
				break;
			}else if(i < nums.length - 1 && nums[i] + 1 < nums[i + 1]){
				result = nums[i] + 1;
				break;
			}else if(i == nums.length - 1){
				result = nums[i] + 1;
				break;
			}
		}

		return result;
	}

	public int firstMissingPositive2(int[] A) {
		int i = 0;
		while (i < A.length) {
			while (A[i] > 0 && A[i] < A.length && A[A[i] - 1] != A[i]) {
				swap(A, A[i] - 1, i);

			}
			i++;
		}
		i = 0;
		while (i < A.length && A[i] == i + 1) {
			i++;
		}
		return i + 1;
	}

	private void swap(int[] A, int i, int j){
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}

}
